//找到最短k条路径的方法，但是未解决死循环问题


#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <set>

using namespace std;

// 存储路径信息的结构体
struct Path {
    vector<size_t> nodes;  // 路径上的节点序列
    size_t length;         // 路径总长度

    // 重载运算符，用于优先队列按路径长度升序排列
    bool operator>(const Path& other) const {
        return length > other.length;
    }
};

// Dijkstra算法：找到从起点到终点的最短路径
vector<size_t> dijkstra(size_t start, size_t end, const vector<vector<size_t>>& roadlength) {
    const size_t INF = INT_MAX;
    const size_t n = roadlength.size();
    vector<size_t> dist(n, INF);  // 存储起点到各节点的最短距离
    dist[start] = 0;
    vector<size_t> prev(n, INF);  // 存储路径的前驱节点

    // 优先队列，按距离升序排列
    priority_queue<pair<size_t, size_t>, vector<pair<size_t, size_t>>, greater<pair<size_t, size_t>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (u == end) break;  // 找到终点，退出循环
        if (d > dist[u]) continue;  // 如果当前距离不是最短，跳过

        // 遍历邻接节点
        for (size_t v = 0; v < n; ++v) {
            if (roadlength[u][v] != INF && dist[v] > dist[u] + roadlength[u][v]) {
                dist[v] = dist[u] + roadlength[u][v];  // 更新最短距离
                prev[v] = u;  // 更新前驱节点
                pq.push({dist[v], v});  // 将节点加入优先队列
            }
        }
    }

    if (dist[end] == INF) return {};  // 如果终点不可达，返回空路径

    // 回溯构建路径
    vector<size_t> path;
    for (size_t cur = end; cur != start; cur = prev[cur]) {
        if (prev[cur] == INF) return {};  // 如果前驱节点无效，返回空路径
        path.push_back(cur);
    }
    path.push_back(start);

    reverse(path.begin(), path.end());  // 反转路径，使其从起点到终点
    return path;
}

// 计算路径的总长度
size_t calculatePathLength(const vector<size_t>& path, const vector<vector<size_t>>& roadlength) {
    size_t length = 0;
    for (size_t i = 0; i < path.size() - 1; ++i) {
        length += roadlength[path[i]][path[i + 1]];  // 累加路径中每条边的长度
    }
    return length;
}

// Yen's Algorithm：找到从起点到终点的前k条最短路径
vector<vector<size_t>> yen_ksp(size_t start, size_t end, size_t k, const vector<vector<size_t>>& roadlength) {
    vector<vector<size_t>> P;  // 存储最终的最短路径集合
    if (k == 0) return P;

    // 找到第一条最短路径
    auto firstPath = dijkstra(start, end, roadlength);
    if (firstPath.empty()) return P;  // 如果不存在路径，返回空集合
    P.push_back(firstPath);

    // 优先队列，按路径长度升序排列
    priority_queue<Path, vector<Path>, greater<Path>> Q;

    // 用于去重，避免生成重复路径
    set<vector<size_t>> usedPaths;
    usedPaths.insert(firstPath);

    // 对第一条路径的每个节点生成偏离路径
    for (size_t i = 0; i < firstPath.size() - 1; ++i) {
        size_t r = firstPath[i];
        size_t s = firstPath[i + 1];

        // 修改邻接矩阵，禁止使用当前边
        vector<vector<size_t>> modified_roadlength = roadlength;
        modified_roadlength[r][s] = INT_MAX;
        modified_roadlength[s][r] = INT_MAX;

        // 找到从 r 到 end 的最短路径
        auto spurPath = dijkstra(r, end, modified_roadlength);
        if (!spurPath.empty()) {
            // 合并路径
            vector<size_t> newPath(firstPath.begin(), firstPath.begin() + i + 1);
            newPath.insert(newPath.end(), spurPath.begin() + 1, spurPath.end());

            // 计算新路径的长度
            size_t newLen = calculatePathLength(newPath, roadlength);

            // 如果路径未重复，加入优先队列
            if (!usedPaths.count(newPath)) {
                usedPaths.insert(newPath);
                Q.push({newPath, newLen});
            }
        }
    }

    // 继续生成路径，直到找到 k 条或没有更多路径
    while (!Q.empty() && P.size() < k) {
        Path candidate = Q.top();
        Q.pop();

        // 检查路径是否已存在于结果中
        bool duplicate = false;
        for (auto &p : P) {
            if (p == candidate.nodes) {
                duplicate = true;
                break;
            }
        }
        if (duplicate) continue;

        // 将路径加入结果集合
        P.push_back(candidate.nodes);

        // 对当前路径生成偏离路径
        for (size_t i = 0; i < candidate.nodes.size() - 1; ++i) {
            size_t r = candidate.nodes[i];
            size_t s = candidate.nodes[i + 1];

            // 修改邻接矩阵，禁止使用当前边
            vector<vector<size_t>> modified_roadlength = roadlength;
            modified_roadlength[r][s] = INT_MAX;
            modified_roadlength[s][r] = INT_MAX;

            // 找到从 r 到 end 的最短路径
            auto spurPath = dijkstra(r, end, modified_roadlength);
            if (!spurPath.empty()) {
                // 合并路径
                vector<size_t> newPath(candidate.nodes.begin(), candidate.nodes.begin() + i + 1);
                newPath.insert(newPath.end(), spurPath.begin() + 1, spurPath.end());

                // 计算新路径的长度
                size_t newLen = calculatePathLength(newPath, roadlength);

                // 如果路径未重复，加入优先队列
                if (!usedPaths.count(newPath)) {
                    usedPaths.insert(newPath);
                    Q.push({newPath, newLen});
                }
            }
        }
    }

    return P;
}

// 事件结构，用于模拟车辆行驶过程
struct Event {
    size_t time;  // 事件发生的时刻
    size_t u;     // 起始节点
    size_t v;     // 结束节点
    bool enter;   // true 表示车辆进入(u->v)，false 表示车辆离开(u->v)

    // 重载运算符，用于优先队列按时间升序排列
    bool operator>(const Event& other) const {
        return time > other.time;
    }
};

// 检查当前车辆组合是否会导致堵车
bool checkTraffic(const vector<vector<size_t>>& combination,
                  const vector<vector<size_t>>& roadlength,
                  const vector<vector<size_t>>& restrictions) {
    // 优先队列，按时间升序排列
    priority_queue<Event, vector<Event>, greater<Event>> eventQueue;

    // 将每辆车的行驶过程转化为事件
    for (const auto& path : combination) {
        size_t current_time = 0;
        for (size_t i = 1; i < path.size(); ++i) {
            size_t u = path[i - 1];
            size_t v = path[i];
            size_t length = roadlength[u][v];

            // 车辆进入(u->v)的事件
            eventQueue.push({current_time, u, v, true});
            // 车辆离开(u->v)的事件
            eventQueue.push({current_time + length, u, v, false});

            current_time += length;
        }
    }

    // 记录当前每条道路的流量
    vector<vector<size_t>> current_flow(roadlength.size(), vector<size_t>(roadlength.size(), 0));

    // 处理事件
    while (!eventQueue.empty()) {
        size_t current_time = eventQueue.top().time;

        // 收集同一时刻的所有事件
        vector<Event> sameTimeEvents;
        while (!eventQueue.empty() && eventQueue.top().time == current_time) {
            sameTimeEvents.push_back(eventQueue.top());
            eventQueue.pop();
        }

        // 先处理离开事件，释放流量
        for (auto &event : sameTimeEvents) {
            if (!event.enter) {
                if (current_flow[event.u][event.v] > 0) {
                    current_flow[event.u][event.v]--;
                    current_flow[event.v][event.u]--;
                }
            }
        }

        // 再处理进入事件，增加流量
        for (auto &event : sameTimeEvents) {
            if (event.enter) {
                current_flow[event.u][event.v]++;
                current_flow[event.v][event.u]++;
                if (current_flow[event.u][event.v] > restrictions[event.u][event.v]) {
                    return false;  // 流量超限，发生堵车
                }
            }
        }
    }

    return true;  // 所有事件处理完毕，未发生堵车
}

// 计算当前组合的总路径长度
size_t calculateTotalLength(const vector<vector<size_t>>& combination,
                            const vector<vector<size_t>>& roadlength) {
    size_t total_length = 0;
    for (const auto &path : combination) {
        for (size_t i = 1; i < path.size(); i++) {
            size_t u = path[i - 1];
            size_t v = path[i];
            total_length += roadlength[u][v];  // 累加每条边的长度
        }
    }
    return total_length;
}

// 回溯遍历所有车辆路径组合
void traverseCombinations(const vector<vector<vector<size_t>>>& all_cars_paths,
                          size_t car_index,
                          vector<vector<size_t>>& current_combination,
                          const vector<vector<size_t>>& roadlength,
                          const vector<vector<size_t>>& restrictions,
                          vector<vector<size_t>>& best_combination,
                          size_t& min_total_length) {
    // 如果已经处理完所有车辆，检查当前组合是否最优
    if (car_index == all_cars_paths.size()) {
        if (checkTraffic(current_combination, roadlength, restrictions)) {
            size_t total_length = calculateTotalLength(current_combination, roadlength);
            if (total_length < min_total_length) {
                min_total_length = total_length;
                best_combination = current_combination;
            }
        }
        return;
    }

    // 遍历当前车辆的所有候选路径
    for (const auto &path : all_cars_paths[car_index]) {
        current_combination.push_back(path);
        // 递归处理下一辆车
        traverseCombinations(all_cars_paths, car_index + 1, current_combination,
                             roadlength, restrictions, best_combination,
                             min_total_length);
        // 回溯，撤销选择
        current_combination.pop_back();
    }
}

// 找到不堵车且总路径长度最短的组合
void findBestCombination(const vector<vector<vector<size_t>>>& all_cars_paths,
                         const vector<vector<size_t>>& roadlength,
                         const vector<vector<size_t>>& restrictions) {
    vector<vector<size_t>> best_combination;
    size_t min_total_length = INT_MAX;

    // 回溯遍历所有组合
    vector<vector<size_t>> current_combination;
    traverseCombinations(all_cars_paths, 0, current_combination,
                         roadlength, restrictions, best_combination,
                         min_total_length);

    // 输出最优组合
    if (!best_combination.empty()) {
        cout << "Best combination (total length: " << min_total_length << "):\n";
        for (size_t i = 0; i < best_combination.size(); i++) {
            cout << "Car " << i + 1 << " path: ";
            for (size_t node : best_combination[i]) {
                cout << node + 1 << " ";
            }
            cout << "\n";
        }
    } else {
        cout << "No valid combination found!\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    size_t N, M;
    cin >> N >> M;

    // 邻接矩阵，存储道路长度
    vector<vector<size_t>> roadlength(N, vector<size_t>(N, INT_MAX));
    // 流量限制矩阵
    vector<vector<size_t>> restrictions(N, vector<size_t>(N, 0));
    // 每辆车的起点和终点
    vector<vector<size_t>> cars(M, vector<size_t>(2));

    // 读取道路长度矩阵
    for (size_t i = 0; i < N; ++i) {
        for (size_t j = 0; j < N; ++j) {
            cin >> roadlength[i][j];
            if (roadlength[i][j] == 0 && i != j) {
                roadlength[i][j] = INT_MAX;  // 0 表示不可达
            }
        }
    }

    // 读取流量限制矩阵
    for (size_t i = 0; i < N; ++i) {
        for (size_t j = 0; j < N; ++j) {
            cin >> restrictions[i][j];
        }
    }

    // 读取每辆车的起点和终点
    for (size_t i = 0; i < M; ++i) {
        cin >> cars[i][0] >> cars[i][1];
        cars[i][0]--;  // 转换为 0-based 索引
        cars[i][1]--;
    }

    // 计算每辆车的候选路径数量 k
    size_t k = (size_t)pow(SIZE_MAX, 1.0 / M);

    // 存储每辆车的候选路径
    vector<vector<vector<size_t>>> all_cars_paths(M);
    printf("113\n");
    // 为每辆车生成前 k 条最短路径
    for (size_t i = 0; i < M; ++i) {
        size_t start = cars[i][0];
        size_t end = cars[i][1];

        auto paths = yen_ksp(start, end, k, roadlength);

        if (paths.empty()) {
            cerr << "Warning: Car " << i + 1 << " cannot reach its destination!\n";
        }

        all_cars_paths[i] = paths;
    }
    printf("123\n");
    // 找到最优组合
    findBestCombination(all_cars_paths, roadlength, restrictions);

    return 0;
}